package 华为OD机试真题2023.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class HJ20_组装新的数组 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/20.txt"));
        MyUtil.START();
        Solution(in);
        //        Solution2(in);
        MyUtil.END();
    }

    static int result = 0;
    static LinkedList<Integer> path = new LinkedList<>();

    static void Solution(Scanner in) {
        String[] sArray = in.nextLine().split(" ");
        int total = in.nextInt();
        int[] nums = new int[sArray.length];
        for (int i = 0; i < sArray.length; i++) {
            nums[i] = Integer.parseInt(sArray[i]);
        }
        Arrays.sort(nums);
        dfs(nums, 0, total);
        System.out.println(result);
    }

    static void dfs(int[] nums, int startIndex, int target) {
        if (target < nums[0]) {
            if (target != 0) {
                path.addLast(target);
            }
            System.out.println(path);
            result++;
            if (target != 0) { // 注意，递归里的操作一定要成对出现！
                path.removeLast();
            }
            return;
        }
        if (startIndex == nums.length) {
            return;
        }
        int now = nums[startIndex];
        for (int j = 0; j * now <= target; j++) {
            for (int k = 0; k < j; k++) {
                path.addLast(now);
            }
            dfs(nums, startIndex + 1, target - j * now);
            for (int k = 0; k < j; k++) {
                path.removeLast();
            }
        }
    }

    public static int max;
    public static int min;
    public static int res;

    static void Solution2(Scanner sc) {
        String[] strings = sc.nextLine().split(" ");
        int M = sc.nextInt();
        min = Integer.valueOf(strings[0]); // 数组中的最小数
        max = Integer.valueOf(strings[strings.length - 1]); // 数组中的最大数
        handle(min, M);
        System.out.println(res);
    }

    /**
     * @param n 数组中的数字
     * @param sum M减去数组中的数字的差值
     */
    public static void handle(int n, int sum) {
        if (sum < min) { // 剩下的小于最小数就可以组装（符合第三个规则）
            res++;
            return;
        }
        if (n > max) { // 大于最大数则返回
            return;
        }
        int i = 0;
        while (true) {
            handle(n + 1, sum - i * n); // 因为数组中的数字是连续的，所以只需要+1
            i++;
            if (sum - i * n <= 0) {
                if (sum - i * n == 0) { // 完美符合
                    res++;
                }
                break;
            }
        }
    }
}
